package org.hmh.offer;

import java.util.ArrayList;

/**
 * Created this one by HMH on 2018/1/20.
 */
public class t24 {
    static class Solution {
        public ArrayList<String> Permutation(String str) {
            ArrayList<String> res = new ArrayList<>();
            if (str == null || str.length() == 0) return res;
            permutation(str.toCharArray(), 0, res);
            return res;
        }

        public void permutation(char[] chars, int start, ArrayList<String> res) {
            if (start == chars.length - 1) {
                res.add(new String(chars));
            }
            for (int j = start; j < chars.length; j++) {
                if( j == start || chars[start] != chars[j]){
                    swap(chars, start, j);
                    permutation(chars, start + 1, res);
                    swap(chars, start, j);
                }
            }

        }

        private void swap(char[] chars, int i, int j) {
            char temp = chars[i];
            chars[i] = chars[j];
            chars[j] = temp;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();

        System.out.println(solution.Permutation("aa"));
    }
}
